package LinkedList;

public class p19删除链表的倒数第N个节点 {
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode fast = head;
            ListNode slow = head;
            int count = 0;
            while(fast.next != null){
                fast = fast.next;
                if(count >= n){
                    slow = slow.next;
                }
                count++;
            }
            if(count < n){
                return head.next;
            }
            slow.next = slow.next.next;
            return head;
        }
    }

    class Solution2 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            int length = 1;
            ListNode p = head;
            while(p.next != null){
                p = p.next;
                length++;
            }
            int index = length - n;
            if(index == 0){
                return head.next;
            }
            ListNode t = head;
            for(int i = 1; i < index; i++){
                t = t.next;
            }
            t.next = t.next.next;
            return head;
        }
    }
}
